# encoding = utf-8
# k_neighbor   https://blog.csdn.net/winter_evening/article/details/70196080
import pandas as pd
from pandas import Series, DataFrame


class TreeNode:
    def __init__(self, parent_index, index, point, left, right):
        self.parent_index = parent_index
        self.index = index
        self.point = point
        self.left = left
        self.right = right


class BinaryTree:
    def createTree(self, point_list, parent_index=-1):
        column_count = point_list.shape[1]
        row_count = point_list.shape[0]
        index = (parent_index + 1) % column_count

        if row_count == 1:
            return TreeNode(parent_index, index,
                            point_list.iloc[0].values, None, None)

        point_list = point_list.sort_values(by=index)
        median_index = int(row_count / 2)
        median = point_list.iloc[median_index].values

        left = self.createTree(point_list.iloc[:median_index], index)
        if median_index + 1 == row_count:
            right = None
        else:
            right = self.createTree(point_list.iloc[(median_index + 1):], index)

        return TreeNode(parent_index, index, median, left, right)

    def getNode(self, node, point):
        if (point[node.index] <= node.point[node.index]):
            if (node.left == None):
                return node
            else:
                return self.getNode(node.left, point)
        elif (point[node.index] >= node.point[node.index]):
            if (node.right == None):
                return node
            else:
                return self.getNode(node.right, point)

    def findNeighbor(self, tree, point=[2, 3]):
        data = self.getNode(tree, point)
        print(data.point)


data = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]

result = DataFrame(data)

tree = BinaryTree().createTree(result)
BinaryTree().findNeighbor(tree)

# print(result)
# print("........")
# index = 0
# print(result.sort_values(by=0))
# print("........")
# index = 1

# print(result.iloc[4:])
# print(result.iloc[:3])

# print(result.columns.values)

# print(result.sort_values(by=index))
